//Given a string s, find the length of the longest substring without repeating c
//haracters. 
//
// 
// Example 1: 
//
// 
//Input: s = "abcabcbb"
//Output: 3
//Explanation: The answer is "abc", with the length of 3.
// 
//
// Example 2: 
//
// 
//Input: s = "bbbbb"
//Output: 1
//Explanation: The answer is "b", with the length of 1.
// 
//
// Example 3: 
//
// 
//Input: s = "pwwkew"
//Output: 3
//Explanation: The answer is "wke", with the length of 3.
//Notice that the answer must be a substring, "pwke" is a subsequence and not a 
//substring.
// 
//
// Example 4: 
//
// 
//Input: s = ""
//Output: 0
// 
//
// 
// Constraints: 
//
// 
// 0 <= s.length <= 5 * 104 
// s consists of English letters, digits, symbols and spaces. 
// 
// Related Topics 哈希表 双指针 字符串 Sliding Window 
// 👍 5444 👎 0


package leetcode.editor.cn;

import java.util.*;

//Java：Longest Substring Without Repeating Characters
class P3LongestSubstringWithoutRepeatingCharacters {
    public static void main(String[] args) {
        Solution solution = new P3LongestSubstringWithoutRepeatingCharacters().new Solution();
        solution.lengthOfLongestSubstringSet("abcabcd");
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        public int lengthOfLongestSubstring(String str) {
            if (str == null || str.length() == 0) {
                return 0;
            }
            char[] arr = str.toCharArray();
            List<Character> store = new ArrayList<>();
            int j = 0;
            String max = arr[0] + "";
            for (int i = 0; i < arr.length; i++) {
                char ch = arr[i];
                if (store.contains(ch)) {
                    store.remove((Character) arr[j++]);
                    i--;
                } else {
                    store.add(ch);
                }
                if (store.size() > max.length()) {
                    max = str.substring(j, i + 1);
                }
            }
            return max.length();
        }

        //2.滑动窗口
        public int lengthOfLongestSubstringSet(String s) {
            // 哈希集合，记录每个字符是否出现过
            Set<Character> occ = new HashSet<Character>();
            int n = s.length();
            // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
            int rk = -1, ans = 0;
            for (int i = 0; i < n; ++i) {
                if (i != 0) {
                    // 左指针向右移动一格，移除一个字符
                    occ.remove(s.charAt(i - 1));
                }
                while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                    // 不断地移动右指针
                    occ.add(s.charAt(rk + 1));
                    ++rk;
                }
                // 第 i 到 rk 个字符是一个极长的无重复字符子串
                ans = Math.max(ans, rk - i + 1);
            }
            return ans;
        }
        public  int lengthOfLongestSubstringMap(String s) {
            LinkedHashMap<String, Integer> map = new LinkedHashMap();
            int max = 0;
            for (int i = 0; i < s.length(); i++) {
                String str = s.substring(i, i + 1);
                if (map.size() == 0) {
                    map.put(str, i);
                    continue;
                }
                if (map.get(str) == null) {
                    map.put(str, i);
                } else {
                    if (map.size() > max) {
                        max = map.size();
                    }
                    int index = map.get(str);
                    Iterator<String> iterator = map.keySet().iterator();
                    while (iterator.hasNext()) {
                        String next = iterator.next();
                        Integer integer = map.get(next);
                        if (integer < index) {
                            iterator.remove();
                        } else if (integer == index) {
                            break;
                        }
                    }
                    map.put(str, i);
                }
            }
            if (!map.isEmpty() && map.size() > max) {
                max = map.size();
            }
            return max;
        }

        public  int lengthOfLongestSubstringMax(String s) {
            LinkedHashMap<String, Integer> map = new LinkedHashMap();
            int max = 0;
            int j = 0;
            if (s.isEmpty()) {
                return 0;
            }
            if (s.length() == 1) {
                return 1;
            }
            for (int i = 0; i < s.length(); i++) {
                String str = s.substring(i, i + 1);
                if (map.containsKey(str)) {
                    j = Math.max(j, map.get(str));
                }
                map.put(str, i);
                max = Math.max(max, i - j);

            }

            return max;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}